package daily_exercise;

import java.util.*;

public class Demo7 {

    // 3211. 生成不含相邻零的二进制字符串
    private StringBuilder path;
    private List<String> res;

    public List<String> validStrings(int n) {
        path = new StringBuilder();
        res = new ArrayList<>();
        dfs(0, n);
        return res;
    }
    private void dfs(int pos, int n) {
        if (pos == n) {
            res.add(path.toString());
            return;
        }
        // 0 只能处于第一个位置，或者前一个数字为 1 时才能放 0
        if (pos == 0 || pos > 0 && path.charAt(pos - 1) == '1') {
            path.append('0');
            dfs(pos + 1, n);
            path.deleteCharAt(path.length() - 1);
        }
        path.append('1');
        dfs(pos + 1, n);
        path.deleteCharAt(path.length() - 1);
    }



    // 3216. 交换后字典序最小的字符串
    public String getSmallestString(String s) {
        // 贪心：交换前面的
        StringBuilder res = new StringBuilder(s);
        int n = res.length();
        for (int i = 0; i < n - 1; i++) {
            int num1 = s.charAt(i) - '0', num2 = s.charAt(i + 1) - '0';
            if (num1 <= num2 || num1 % 2 != num2 % 2) {
                continue;
            }
            res.setCharAt(i, (char)(num2 + '0'));
            res.setCharAt(i + 1, (char)(num1 + '0'));
            break;
        }
        return res.toString();
    }




    // 3259. 超级饮料的最大强化能量
    public long maxEnergyBoost(int[] energyDrinkA, int[] energyDrinkB) {
        int n = energyDrinkA.length;
        // 0代表继续喝当前饮料， 1 代表切换饮料
        long a0 = 0, a1 = 0, b0 = 0, b1 = 0;
        for (int i = 0; i < n; i++) {
            long tmpA0 = a0, tmpA1 = a1, tmpB0 = b0, tmpB1 = b1;
            // 上一次喝的是 A 饮料，或者上一次没有喝饮料且是从 B 饮料切换过来的
            a0 = Math.max(tmpA0 , tmpB1) + energyDrinkA[i];
            // 上一次喝的是 B 饮料，或者上一次没有喝饮料且是从 A 饮料切换过来的
            b0 = Math.max(tmpB0, tmpA1) + energyDrinkB[i];
            // 这一次不喝饮料，总能量与上一次一样
            a1 = tmpA0;
            b1 = tmpB0;
        }
        return Math.max(a0, b0);
    }



    // 3226. 使两个整数相等的位更改次数
    public int minChanges(int n, int k) {
        if (n == k) return 0;
        if (n < k) return -1;
        // n 为 1 的二进制位 k 必须也为 1，k 为 0 的二进制位 n 可能转为 0
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int x = (n>>i) & 1;
            int y = (k>>i) & 1;
            if (x == 0 && y == 1) return -1;
            if (y == 0 && x == 1) res++;
        }
        return res;
    }


    // 638. 大礼包
    Map<String, Integer> memo = new HashMap<>();  // 记忆化存储
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return dfs(price, special, needs);
    }
    private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        // 将当前的 needs 作为 HashMap 的键
        String key = needs.toString();
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int n = price.size();
        // 1. 原价购买
        int minTotal = 0;
        for (int i = 0; i < n; i++) {
            minTotal += needs.get(i) * price.get(i);
        }
        // 2. 枚举每一个大礼包
        for (List<Integer> gift : special) {
            boolean canBuy = true;
            for (int i = 0; i < n; i++) {
                if (gift.get(i) > needs.get(i)) {
                    canBuy = false;
                    break;
                }
            }
            if (canBuy) {
                computeNeeds(needs, gift, '-');
                minTotal = Math.min(minTotal, gift.get(n) + dfs(price, special, needs)) ;
                computeNeeds(needs, gift, '+');
            }
        }

        memo.put(key, minTotal);
        return memo.get(key);
    }
    private void computeNeeds(List<Integer> needs, List<Integer> gift, char option) {
        int flag = 1;
        if (option == '-') flag = -1;
        int n = needs.size();
        for (int i = 0; i < n; i++) {
            needs.set(i, needs.get(i) + gift.get(i) * flag);
        }
    }



    // 633. 平方数之和
    public boolean judgeSquareSum(int c) {
        int a = 0, b = (int)Math.sqrt(c);
        while (a <= b) {
            if ((long) a * a + (long) b * b == c) return true;
            else if ((long)a * a + (long)b * b > c) b--;
            else a++;
        }
        return false;
    }


    public String losingPlayer(int x, int y) {
        int res = 0;
        while (x >= 1 && y >= 4) {
            res++;
            x--;
            y -= 4;
        }
        return res % 2 == 1 ? "Alice" : "Bob";
    }



    // 3254. 长度为 K 的子数组的能量值 I
    public static int[] resultsArray(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }

        int left = 0, right = 0;
        int n = nums.length;
        int[] res = new int[n - k + 1];
        while (left < n - k + 1) {
            // left ~ tmp-1 能量值都为 -1
            int tmp = Math.min(right, n - k + 1);
            while (right > 0 && left < tmp && nums[right] != 1 + nums[right - 1]) {
                res[left++] = -1;
            }

            if (right - left + 1 == k && nums[right] == 1 + nums[right - 1]) {
                res[left++] = nums[right];
            }
            right++;
        }
        return res;
    }



    // 3255. 长度为 K 的子数组的能量值 II
    public int[] resultsArray2(int[] nums, int k) {
        if (k == 1) return nums;
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int left = 0, right = 0;
        while (left < n - k + 1) {
            int tmp = Math.min(right, n - k + 1);
            while (right > 0 && left < tmp && nums[right - 1] + 1 != nums[right]) {
                res[left++] = -1;
            }
            if (right - left + 1 == k && nums[right - 1] + 1 == nums[right]) {
                res[left++] = nums[right];
            }
            right++;
        }
        return res;
    }



    // 3242. 设计相邻元素求和服务
    class NeighborSum {
        int n;
        int[][] indexs;
        int[][] nums;
        int[] dx1 = {0,0,1,-1};
        int[] dy1 = {1,-1,0,0};
        int[] dx2 = {-1,-1,1,1};
        int[] dy2 = {-1,1,-1,1};

        public NeighborSum(int[][] grid) {
            n = grid.length;
            this.nums = grid;
            indexs = new int[n * n][2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int num = grid[i][j];
                    indexs[num][0] = i;
                    indexs[num][1] = j;
                }
            }
        }

        public int adjacentSum(int value) {
            int i = indexs[value][0], j = indexs[value][1];
            int res = 0;
            for (int k = 0; k < 4; k++) {
                int x = i + dx1[k], y = j + dy1[k];
                if (x >= 0 && x < n && y >= 0 && y < n) {
                    res += nums[x][y];
                }
            }
            return res;
        }

        public int diagonalSum(int value) {
            int i = indexs[value][0], j = indexs[value][1];
            int res = 0;
            for (int k = 0; k < 4; k++) {
                int x = i + dx2[k], y = j + dy2[k];
                if (x >= 0 && x < n && y >= 0 && y < n) {
                    res += nums[x][y];
                }
            }
            return res;
        }
    }




    // 540. 有序数组中的单一元素
    public int singleNonDuplicate(int[] nums) {
        if (nums.length == 1) return nums[0];
        // 在区间 0 ~ i 中，若没有出现单数，则出现两次的数字中第一个数字的下标为 2 的倍数
        int n = nums.length;
        int left = 0, right = n - 1, mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (mid > 0 && nums[mid] == nums[mid - 1]) {
                if ((mid - 1) % 2 == 0) {
                    left = mid + 1;
                } else {
                    right = mid - 2;
                }
            } else if (mid + 1 < n && nums[mid] == nums[mid + 1]) {
                if (mid % 2 == 0) {
                    left = mid + 2;
                } else {
                    right = mid - 1;
                }
            } else {
                // 位于中间且恰好是那个“单数”
                // 位于首位位置，且恰好是那个“单数”
                return nums[mid];
            }
        }
        return nums[left];
    }




    // 3258. 统计满足 K 约束的子字符串数量 I
    public int countKConstraintSubstrings(String s, int k) {
        int zeroCount = 0, oneCount = 0;
        int left = 0, right = 0, n = s.length();
        int res = 0;
        while (right < n) {
            if (s.charAt(right) == '1') oneCount++;
            else zeroCount++;

            while (left <= right && oneCount > k && zeroCount > k) {
                if (s.charAt(left) == '1') oneCount--;
                else zeroCount--;
                left++;
            }
            // 此时 left ~ right的子字符串一定符合条件
            // 计算以 right 为结尾的子字符串有多少个满足条件
            res += right - left + 1;
            right++;
        }
        return res;
    }




    // 3239. 最少翻转次数使二进制矩阵回文 I
    public int minFlips(int[][] grid) {
        // 1. 先统计行都是回文的翻转次数
        int n = grid.length, m = grid[0].length;
        int res = Integer.MAX_VALUE;
        int count = 0;
        for (int i = 0; i < n; i++) {
            int left = 0, right = m - 1;
            while (left < right) {
                if (grid[i][left] != grid[i][right]) count++;
                left++;
                right--;
            }
        }
        res = Math.min(res, count);

        // 2. 再统计列都是回文的翻转次数
        count = 0;
        for (int j = 0; j < m; j++) {
            int top = 0, bottom = n - 1;
            while (top < bottom) {
                if (grid[top][j] != grid[bottom][j]) count++;
                top++;
                bottom--;
            }
        }
        return Math.min(res, count);
    }




    // 661. 图片平滑器
    public int[][] imageSmoother(int[][] img) {
        int[] dx = {-1,-1,-1,0,0,0,1,1,1};
        int[] dy = {-1,0,1,-1,0,1,-1,0,1};

        int n = img.length, m = img[0].length;
        int[][] res = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int sum = 0, count = 0;
                for (int k = 0; k < 9; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m) {
                        sum += img[x][y];
                        count++;
                    }
                }
                res[i][j] = sum / count;
            }
        }
        return res;
    }



    // 3233. 统计不是特殊数字的数字数量
    public int nonSpecialCount(int l, int r) {
        int primeNumCount = 0;
        int right = (int)Math.sqrt(r);
        for (int i = 2; i <= right; i++) {
            boolean flag = true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag && i * i >= l && i * i <= r) primeNumCount++;
        }
        return r - l + 1 - primeNumCount;
    }




    // 3238. 求出胜利玩家的数目
    public int winningPlayerCount(int n, int[][] pick) {
        int[][] hash = new int[n][11];
        boolean[] vis = new boolean[n];
        int res = 0;
        for (int[] arr : pick) {
            int x= arr[0], y = arr[1];
            if (++hash[x][y] > x && !vis[x]) {
                res++;
                vis[x] = true;
            }
        }
        return res;
    }



    // 743. 网络延迟时间
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] outs = new List[n + 1];
        Arrays.setAll(outs, i-> new ArrayList<>());
        for (int[] time : times) {
            int x = time[0], y = time[1], z = time[2];
            outs[x].add(new int[]{y, z});
        }
        // dijkstra 算法
        // 记录节点 k 发出信号传送到其他节点的最短时间
        int[] minTime = new int[n + 1];
        Arrays.fill(minTime, 0x3f3f3f3f);
        minTime[k] = 0;
        // 记录节点是否已加入最短路径中
        boolean[] vis = new boolean[n + 1];

        // n 趟将 n 个节点加入最短路径中
        for (int i = 1; i <= n; i++) {
            int cur = -1;
            int minVal = 0x3f3f3f3f;
            // 寻找未加入最短路径且距离源点最近的节点
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && minTime[j] < minVal) {
                    cur = j;
                    minVal = minTime[j];
                }
            }
            // 到达不了所有节点
            if (cur == -1) return -1;

            vis[cur] = true;
            for (int[] arr : outs[cur]) {
                int time = arr[1], target = arr[0];
                if (minVal + time < minTime[target]) {
                    minTime[target] = minVal + time;
                }
            }
        }

        // 寻找最长时间
        int res = -1;
        for (int i = 1; i <= n; i++) {
            if (i != k && minTime[i] > res) {
                res = minTime[i];
            }
        }
        return res;
    }



    // 3206. 交替组 I
    public int numberOfAlternatingGroups(int[] colors) {
        int res = 0, n = colors.length;
        int x = -1, y = -1, z = -1;
        for (int i = 0; i < n; i++) {
            x = colors[i]; y = colors[(i + 1) % n]; z = colors[(i + 2) % n];
            if (x == z && x != y) res++;
        }
        return res;
    }


    // 3208. 交替组 II
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int left = 0, right = 1;
        boolean flag = false;   // 标志 right 是否已经走过一圈
        while (left < n) {
            int x = colors[right], y = right == 0 ? colors[n - 1] : colors[right - 1];
            if (x % 2 == y % 2) {
                if (flag) return res;
                left = right;
            }

            int distances = right + n - left + 1;
            if (distances > n) distances -= n;
            if (distances == k) {
                res++;
                left++;
            }
            if (right + 1 == n) flag = true;
            right = (right + 1) % n;
        }
        return res;
    }


    // 3232. 判断是否可以赢得数字游戏
    public boolean canAliceWin(int[] nums) {
        int oneSum = 0, twoSum = 0, sum = 0;
        for (int x : nums) {
            if (x >= 1 && x <= 9) {
                oneSum += x;
            } else if (x > 9 && x < 100) {
                twoSum += x;
            }
            sum += x;
        }
        return oneSum > sum - oneSum || twoSum > sum - twoSum;
    }




    // 3001. 捕获黑皇后需要的最少移动次数
    public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        // 车捕获皇后
        if (a == e && (c != a || d > Math.max(b, f) || d < Math.min(b, f))) return 1;
        if (b == f && (d != b || c > Math.max(a ,e) || c < Math.min(a, e))) return 1;
        // 象捕获皇后
        if (c + d == e + f) {
            if (c + d != a + b) return 1;
            if (!(a > Math.min(c, e) && a < Math.max(c, e))) return 1;
        }
        if (d - c == f - e) {
            if (d - c != b - a) return 1;
            if (!(a > Math.min(c, e) && a < Math.max(c, e))) return 1;
        }
        return 2;
    }



    // 999. 可以被一步捕获的棋子数
    public int numRookCaptures(char[][] board) {
        int n = board.length, m = board[0].length;
        int x = 0, y = 0;
        while (x < n) {
            boolean flag = false;
            for (y = 0; y < m; y++) {
                if (board[x][y] == 'R') {
                    flag = true;
                    break;
                }
            }
            if (flag) break;
            x++;
        }

        int res = 0;
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        for (int k = 0; k < 4; k++) {
            int toX = dx[k], toY = dy[k];
            for (int i = x + toX, j = y + toY; i >= 0 && i < n && j >= 0 && j < m; i += toX, j += toY) {
                if (board[i][j] == 'p') {
                    res++;
                    break;
                }
                if (board[i][j] == 'B') {
                    break;
                }
            }
        }
        return res;
    }



    // 3274. 检查棋盘方格颜色是否相同
    public boolean checkTwoChessboards(String coordinate1, String coordinate2) {
        int x1 = coordinate1.charAt(1), x2 = coordinate2.charAt(1);
        int y1 = coordinate1.charAt(0) - 'a', y2 = coordinate2.charAt(0) - 'a';
        return (x1 + y1) % 2 == (x2 + y2) % 2
                || (y1 - x1) % 2 == (y2 - x2) % 2;

    }



    // 2717. 半有序排列
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        if (nums[0] == 1 && nums[n - 1] == n) return 0;
        int minIndex = -1, maxIndex = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) minIndex = i;
            if (nums[i] == n) maxIndex = i;
        }

        int res = minIndex + n - maxIndex - 1;
        if (minIndex > maxIndex) res--;
        return res;
    }



    // 1812. 判断国际象棋棋盘中一个格子的颜色
    public boolean squareIsWhite(String coordinates) {
        // y = x + b
        // b % 2 == 0  =>黑色    b % 2 == 1 =>白色
        int x = coordinates.charAt(0) - 'a' + 1;
        int y = coordinates.charAt(1) - '0';
        return Math.abs(y - x) % 2 == 1;

    }

    // 51. N 皇后
    class Solution {
        private List<List<String>> res;
        private List<String> path;
        boolean[] rows, cols;
        boolean[] a, b;
        StringBuilder example = new StringBuilder();

        public List<List<String>> solveNQueens(int n) {
            res = new ArrayList<>();
            path = new ArrayList<>();
            rows = new boolean[n]; cols = new boolean[n];     // 横竖方向
            a = new boolean[2 * n]; b = new boolean[2 * n];   // 对角线
            for (int i = 0; i < n; i++) example.append('.');

            dfs(0, n);
            return res;
        }

        private void dfs(int j, int n) {
            if (j == n) {
                res.add(new ArrayList<>(path));
                return;
            }

            for (int i = 0; i < n; i++) {
                if (!cols[j] && !rows[i] && !a[j - i + n] && !b[i + j]) {
                    StringBuilder tmp = new StringBuilder(example);
                    tmp.setCharAt(i, 'Q');
                    cols[j] = rows[i] = a[j - i + n] = b[i + j] = true;
                    path.add(tmp.toString());
                    dfs(j + 1, n);
                    cols[j] = rows[i] = a[j - i + n] = b[i + j] = false;
                    path.remove(path.size() - 1);
                }
            }
        }
    }



    // 1338. 数组大小减半
    public int minSetSize(int[] arr) {
        int[] count = new int[(int)1e5 + 1];
        for (int x : arr) {
            count[x]++;
        }

        int n = arr.length;
        Integer[] indexs = new Integer[(int)1e5 + 1];
        for (int i = 0, sz = indexs.length; i < sz; i++) {
            indexs[i] = i;
        }
        Arrays.sort(indexs, (a, b) -> count[b] - count[a]);

        int res = 0, tmp = n;
        for (int i = 0; i < n; i++) {
            int index = indexs[i];
            tmp -= count[index];
            res++;
            if (tmp <= n / 2) return res;
        }
        return res;
    }
}
